package com.mamingchao.foundation.arraysort.buckesort.radixsort;

import java.util.Arrays;
import java.util.Collections;

/**
 * 一种不需要新建桶，只用一个counter计数数组，就可以实现
 * 要排序几机制的数，就申请长度为几
 *
 * Created by mlamp on 2024/6/27.
 */
public class RadixSort2 {
    // 如果我们做10进制的数的排序，比如[123, 45, 87, 965, 8]
    // 第一步，计算元素里 最长、最多位数是多少位； 然后每个数不够最长位数的，左侧补零-->[123, 045, 087, 965, 008]
    // 第二步，int[] counter = new int[10]; 新增一个10长度的计数器
    // 第三步，个位--> counter的index，按个位对应 counter的index ，把累加的次数放到 counter里；累加后
    // counter计数器的情况为 [0,0,0,1,0,2,0,1,1,0]; 个位是3的有一个，个位 是5的有两个，个位是7的有一个，个位是8的有一个
    //                       0 1 2 3 4 5 6 7 8 9
    // 现在，把counter 每个位置的计数，修改为 <= 这个位置index数的次数[0,0,0,1,1,3,3,4,5,5];从左侧用当前自己位置的数+自己前一个位置的数相加
    //                                                             0 1 2 3 4 5 6 7 8 9
    // 个位<=3的有一个，个位 <=5的有1+2=3，个位 <=6的有3+0=3；个位<=7的有3+1=4，个位<=8的有4+1=5，个位<=9的有5+0=5
    // 新建一个help数组，长度是10，跟counter一样；
    //从右往左遍历原数组；第一个008,8对应counter，找到个位<=8的 计数是5，所以008 放在help数组5的位置，8上面的计数减一
    // [0,0,0,1,1,3,3,4,4,5]    [0,0,0,0,0,8,0,0,0,0];
    //  0 1 2 3 4 5 6 7 8 9      0 1 2 3 4 5 6 7 8 9
    // 重复上面的动作，最后 [0,123,45,965,87,8,0,0,0,0]

    // 再按照十位 重复上面的动作，百位的这样拍
    // 最终完成排序

    public static void main(String[] args) {
        int[] arr = {123, 45, 87, 965, 8};

        // 定义counter计数器
        int[] counter = new int[10];

        // 定义辅助数组，长度也为10
        int[] helperArr = new int[arr.length];

        // 逻辑上是要取数组中元素 最长的位数；事实写代码的时候，比如最长位数是5，当前数是2位；只要取第三位的时候，程序返回0即可，相当于 给所有的数补齐了0
        int numMaxLength = 0;
        for (int i = 0; i < arr.length; i++) {
            //通过第一次遍历，获取数组 所有num 最长的长度值
            int originalNumLength = String.valueOf(arr[i]).length();
            if (originalNumLength > numMaxLength) {
                numMaxLength = originalNumLength;
            }
        }


        boolean useHelpArrForHelp = true;
        // 个位、十位、百位一层一层处理
        // 比如第一层，原始是arr，辅助是helperArr； 第二层，把arr当做辅助，helperArr当做原始数组；通过useHelperArrForHelp 来控制，以此类推
        for (int j = 0; j < numMaxLength; j++) {


            if (useHelpArrForHelp) {
                // 先使用helperArr做辅助数组
                for (int i = 0; i < arr.length; i++) {
                    // 第一次从arr，后面都从helpArr中获取
                    int num = GenereteDigitNumUtil.getDigitNumOtherWay(arr[i], j);
                    counter[num]++;
                }

                // 把counter 每个位置的计数，修改为 <= 这个位置index数的次数
                for (int i = 1; i < counter.length; i++) {
                    counter[i] = counter[i] + counter[i-1] ;
                }

                for (int i = arr.length -1; i > -1; i--) {
                    int num = GenereteDigitNumUtil.getDigitNumOtherWay(arr[i], j);

                    int index = counter[num];
                    helperArr[index-1] = arr[i];
                    counter[num] --;
                }

                for (int i = 0; i < counter.length; i++) {
                    counter[i] = 0 ;
                }

                System.out.println(Arrays.toString(arr));
                System.out.println(Arrays.toString(helperArr));
                System.out.println("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@");

                useHelpArrForHelp = false;
                continue;
            }


            if (!useHelpArrForHelp) {
                // 先使用helperArr做辅助数组
                for (int i = 0; i < helperArr.length; i++) {
                    // 第一次从arr，后面都从helpArr中获取
                    int num = GenereteDigitNumUtil.getDigitNumOtherWay(helperArr[i], j);
                    counter[num]++;
                }

                // 把counter 每个位置的计数，修改为 <= 这个位置index数的次数
                for (int i = 1; i < counter.length; i++) {
                    counter[i] = counter[i] + counter[i-1] ;
                }

                for (int i = helperArr.length -1; i > -1; i--) {
                    int num = GenereteDigitNumUtil.getDigitNumOtherWay(helperArr[i], j);

                    int index = counter[num];
                    arr[index-1] = helperArr[i];
                    counter[num] --;
                }

                for (int i = 0; i < counter.length; i++) {
                    counter[i] = 0 ;
                }

                System.out.println(Arrays.toString(helperArr));
                System.out.println(Arrays.toString(arr));
                System.out.println("-----------------------------------");

                useHelpArrForHelp = true;
                continue;
            }
        }
    }
}
